use log::debug;
use rust_i18n::t;
use std::{
    collections::{HashMap, HashSet, VecDeque},
    sync::Arc,
};
use tokio::sync::Mutex;

use crate::workflow::dag::{
    config::{EdgeConfig, NodeConfig},
    types::WorkflowResult,
};
use crate::workflow::error::WorkflowError;

use super::config::NodeType;

/// 工作流图结构
#[derive(Debug, Clone)]
pub struct WorkflowGraph {
    /// 节点存储（ID到节点的映射）
    nodes: HashMap<String, NodeConfig>,
    /// 节点数量
    node_count: usize,
    /// 边集合
    edges: Vec<EdgeConfig>,
    /// 邻接表
    adjacency_map: HashMap<String, Vec<String>>,
    /// 入度表: 节点 id -> 入度 映射
    in_degree_map: Arc<Mutex<HashMap<String, usize>>>,
}

impl WorkflowGraph {
    /// 创建新图实例（已通过解析器验证隐式边）
    ///
    /// Create a new workflow graph, implicit edges have been generated by the WorkflowParser
    ///
    /// This method initializes a new workflow graph with empty nodes, edges,
    /// adjacency map, and in-degree map. It is the primary constructor for
    /// the WorkflowGraph struct.
    ///
    /// # Arguments
    /// * `nodes` - A vector of NodeConfig instances.
    /// * `edges` - A vector of EdgeConfig instances, already containing both explicit and implicit edges (direct dependencies and edges from child nodes to groups).
    ///
    /// # Returns
    /// * `Self` - Returns a new instance of WorkflowGraph
    pub fn new(nodes: Vec<NodeConfig>, edges: Vec<EdgeConfig>) -> WorkflowResult<Self> {
        // 一次性构建节点映射（保留所有权）
        let node_map: HashMap<_, _> = nodes.into_iter().map(|n| (n.id.clone(), n)).collect();

        // 防御性验证
        for edge in &edges {
            if !node_map.contains_key(&edge.from) || !node_map.contains_key(&edge.to) {
                return Err(WorkflowError::InvalidGraph(
                    t!(
                        "workflow.invalid_graph",
                        reason = t!(
                            "workflow.edge_reference_missing",
                            from = edge.from,
                            to = edge.to
                        )
                        .to_string()
                    )
                    .to_string(),
                ));
            }
        }

        // 重新获取节点集合（保留原始顺序）
        let nodes = node_map.into_values().collect::<Vec<_>>();
        let node_count = nodes.len();

        // 构建邻接表和入度表
        let mut adjacency_map = HashMap::new();
        let mut in_degree_map = HashMap::new();

        nodes.iter().for_each(|n| {
            adjacency_map.insert(n.id.clone(), Vec::new());
            in_degree_map.insert(n.id.clone(), 0);
        });

        edges.iter().for_each(|edge| {
            adjacency_map
                .entry(edge.from.clone())
                .or_insert_with(Vec::new)
                .push(edge.to.clone());

            *in_degree_map.entry(edge.to.clone()).or_insert(0) += 1;
        });

        // 环检测
        Self::detect_cycles(&adjacency_map, &in_degree_map)?;

        Ok(Self {
            nodes: nodes.into_iter().map(|n| (n.id.clone(), n)).collect(),
            node_count,
            edges,
            adjacency_map,
            in_degree_map: Arc::new(tokio::sync::Mutex::new(in_degree_map)),
        })
    }

    /// Detect cycles in the workflow graph
    ///
    /// This method checks if the workflow graph contains any cycles using the Pahn algorithm.
    /// It ensures that the workflow graph is a directed acyclic graph (DAG), which is a requirement for proper workflow execution.
    ///
    /// # Algorithm Details
    /// - Uses the Pahn algorithm to traverse the graph
    /// - Detects cycles by checking the in-degree of nodes
    /// - Returns an error if a cycle is detected
    ///
    /// # Arguments
    /// * `adjacency` - The adjacency list representing the graph connections
    /// * `in_degree` - The in-degree map for the nodes
    ///
    /// # Returns
    /// * `WorkflowResult<()>` - Returns `Ok(())` if no cycles are detected,
    ///   otherwise returns an error with details
    ///
    /// # Errors
    /// * Returns `WorkflowError` if:
    ///   - A cycle is detected in the graph
    fn detect_cycles(
        adjacency: &HashMap<String, Vec<String>>,
        in_degree: &HashMap<String, usize>,
    ) -> WorkflowResult<()> {
        let mut in_degree = in_degree.clone();
        let mut queue = VecDeque::new();
        let mut visited = 0;

        // 初始化队列（入度为0的节点）
        // Find all nodes with zero in-degree
        for (node, degree) in &in_degree {
            if *degree == 0 {
                queue.push_back(node.clone());
            }
        }

        // 拓扑排序处理
        // Traverse the graph using topological sorting
        while let Some(node) = queue.pop_front() {
            visited += 1;

            if let Some(successors) = adjacency.get(&node) {
                for successor in successors {
                    if let Some(degree) = in_degree.get_mut(successor) {
                        *degree -= 1;
                        if *degree == 0 {
                            queue.push_back(successor.clone());
                        }
                    }
                }
            }
        }

        // 环检测结果判断
        // If count is less than the number of nodes, there is a cycle
        if visited != in_degree.len() {
            let cyclic_nodes: Vec<_> = in_degree
                .iter()
                .filter(|(_, d)| **d > 0)
                .map(|(n, _)| n.clone())
                .collect();
            Err(WorkflowError::CircularDependency(cyclic_nodes.join(", ")))
        } else {
            Ok(())
        }
    }

    /// 获取入口节点（入度为0）
    pub async fn entry_nodes(&self) -> Vec<&NodeConfig> {
        let in_degree = self.in_degree_map.lock().await;
        self.nodes
            .values()
            .filter(|n| in_degree.get(&n.id).map(|d| *d == 0).unwrap_or(false))
            .collect()
    }

    /// 获取直接显式后继节点（引用切片）
    pub fn successors(&self, node_id: &str) -> &[String] {
        self.adjacency_map
            .get(node_id)
            .map(|v| v.as_slice())
            .unwrap_or_default()
    }

    /// 获取完整后继节点列表（显式 + 隐式组依赖）
    pub fn all_successors(
        &self,
        node_id: &str,
        child_groups: &HashMap<String, Vec<String>>,
    ) -> Vec<String> {
        let mut successors = self.successors(node_id).to_vec();

        // 添加隐式组依赖
        if let Some(groups) = child_groups.get(node_id) {
            successors.extend_from_slice(groups);
        }

        successors
    }

    /// 获取入度表副本
    pub fn in_degree_map(&self) -> Arc<Mutex<HashMap<String, usize>>> {
        self.in_degree_map.clone()
    }

    pub async fn get_in_degree(&self, node_id: &str) -> Option<usize> {
        self.in_degree_map.lock().await.get(node_id).cloned()
    }

    /// 获取节点配置
    pub fn get_node(&self, node_id: &str) -> Option<&NodeConfig> {
        self.nodes.get(node_id)
    }

    /// 验证所有节点是否完成
    pub fn all_nodes_processed(&self, completed: &HashSet<String>) -> bool {
        self.nodes.keys().all(|id| completed.contains(id))
    }

    /// 调试输出
    #[cfg(debug_assertions)]
    pub async fn debug_print(&self) {
        debug!("Workflow Graph Structure:");
        debug!("Nodes: {}", self.nodes.len());
        for (id, node) in &self.nodes {
            debug!("  [{}] {:?}", id, node.r#type);
        }

        debug!("Edges: {}", self.edges.len());
        for edge in &self.edges {
            debug!("  {} -> {}", edge.from, edge.to);
        }

        debug!("Adjacency Map:");
        for (node, successors) in &self.adjacency_map {
            debug!("  {} => [{}]", node, successors.join(", "));
        }

        debug!("In-Degree Map:");
        for (node, degree) in self.in_degree_map.lock().await.iter() {
            debug!("  {}: {}", node, degree);
        }
    }

    // 访问器
    pub fn nodes(&self) -> impl Iterator<Item = &NodeConfig> {
        self.nodes.values()
    }

    /// 获取节点数量
    pub fn node_count(&self) -> usize {
        self.node_count
    }

    /// 获取邻接表
    pub fn adjacency_map(&self) -> &HashMap<String, Vec<String>> {
        &self.adjacency_map
    }

    pub fn edges(&self) -> &[EdgeConfig] {
        &self.edges
    }

    /// Convert the workflow graph to a Markmap string
    ///
    /// This method generates a Markmap string representation of the workflow graph,
    /// which can be used for visualization. It builds the Markmap structure by
    /// recursively traversing the graph nodes.
    ///
    /// # Returns
    /// * `String` - Returns the Markmap string representation of the workflow graph
    pub async fn to_markmap(&self, status_map: &HashMap<String, &str>, depth: usize) -> String {
        let mut output = String::new();

        // 获取入口节点（入度为0）
        let entries = self.entry_nodes().await;
        for node in entries {
            self.build_markmap_node(&mut output, node, status_map, depth);
        }

        output
    }

    /// Recursively build a Markmap node
    ///
    /// This method builds a Markmap node string for the given node and its children.
    /// It uses the status map to add status icons to the node labels.
    ///
    /// # Arguments
    /// * `output` - A mutable string that will be appended to
    /// * `node` - The configuration of the current node
    /// * `status_map` - A map of node IDs to their corresponding status icons
    /// * `depth` - The current depth of recursion
    ///
    /// # Returns
    /// * `String` - Returns the Markmap node string
    fn build_markmap_node(
        &self,
        output: &mut String,
        node: &NodeConfig,
        status_map: &HashMap<String, &str>,
        depth: usize,
    ) {
        let indent = "  ".repeat(depth);
        let status_icon = status_map.get(&node.id).copied().unwrap_or("");

        // 节点标题行
        let title_line = match &node.r#type {
            NodeType::Group(config) => {
                format!(
                    "{}# {}{} [{}]\n",
                    indent,
                    status_icon,
                    node.id,
                    if config.parallel {
                        "PARALLEL"
                    } else {
                        "SEQUENCE"
                    }
                )
            }
            _ => format!("{}- {}{}\n", indent, status_icon, node.id),
        };
        output.push_str(&title_line);

        // 添加描述信息
        if let Some(desc) = &node.description {
            output.push_str(&format!("{}  *{}*\n", indent, desc));
        }

        // 递归处理子节点（组节点专用）
        if let NodeType::Group(config) = &node.r#type {
            for child_id in &config.nodes {
                if let Some(child) = self.get_node(child_id) {
                    self.build_markmap_node(output, child, status_map, depth + 1);
                }
            }
        }

        // 处理后继节点（非组节点的依赖）
        let successors = self.all_successors(&node.id, &HashMap::new());
        for successor in successors {
            if let Some(successor_node) = self.get_node(&successor) {
                self.build_markmap_node(output, successor_node, status_map, depth + 1);
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::workflow::dag::config::{NodeType, ToolConfig};

    use super::*;

    fn sample_node(id: &str) -> NodeConfig {
        NodeConfig {
            id: id.to_string(),
            r#type: NodeType::Task(ToolConfig::default()),
            timeout_secs: 0,
            description: None,
        }
    }

    #[tokio::test]
    async fn test_valid_graph() {
        let nodes = vec![sample_node("a"), sample_node("b"), sample_node("c")];

        // a -> b -> c
        let edges = vec![
            EdgeConfig {
                from: "a".into(),
                to: "b".into(),
            },
            EdgeConfig {
                from: "b".into(),
                to: "c".into(),
            },
        ];

        let graph = WorkflowGraph::new(nodes, edges).unwrap();
        assert_eq!(graph.entry_nodes().await.len(), 1);
        assert_eq!((graph.entry_nodes().await)[0].id, "a");
    }

    #[test]
    fn test_cycle_detection() {
        let nodes = vec![sample_node("a"), sample_node("b")];

        let edges = vec![
            EdgeConfig {
                from: "a".into(),
                to: "b".into(),
            },
            EdgeConfig {
                from: "b".into(),
                to: "a".into(),
            },
        ];

        match WorkflowGraph::new(nodes, edges) {
            Err(WorkflowError::CircularDependency(nodes)) => {
                assert!(nodes.contains("a") && nodes.contains("b"))
            }
            _ => panic!("Should detect cycle"),
        }
    }

    #[test]
    fn test_missing_node() {
        let nodes = vec![sample_node("a")];
        let edges = vec![EdgeConfig {
            from: "a".into(),
            to: "b".into(),
        }];

        match WorkflowGraph::new(nodes, edges) {
            Err(WorkflowError::InvalidGraph(msg)) => {
                log::error!("{}", msg);
            }
            _ => panic!("Should detect missing node"),
        }
    }
}
